SherbyNet - /page/wikibook/entry.mu

Micron Document

`:top

In `F33f`_`[computing`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computing]`_`f, a `!parallel programming model`! is an `F33f`_`[abstraction`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Abstraction_(software_engineering)]`_`f of `F33f`_`[parallel computer`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Parallel_computing]`_`f architecture, with which it is convenient to express `F33f`_`[algorithms`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Algorithms]`_`f and their composition in `F33f`_`[programs`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_program]`_`f. The value of a programming model can be judged on its `*generality`*: how well a range of different problems can be expressed for a variety of different architectures, and its `*performance`*: how efficiently the compiled programs can execute.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] The implementation of a parallel programming model can take the form of a `F33f`_`[library`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Library_(computing)]`_`f invoked from a `F33f`_`[programming language`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Programming_language]`_`f, as an extension to an existing languages.

Consensus around a particular programming model is important because it leads to different parallel computers being built with support for the model, thereby facilitating `F33f`_`[portability`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Software_portability]`_`f of software. In this sense, programming models are referred to as `*`F33f`_`[bridging`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bridging_model]`_`f`* between hardware and software.`:cite-ref-valiant1990-2-0[`F5bf`_`[2`#cite-note-valiant1990-2]`_`f]

>>Contents

• `F0af`_`[Classification of parallel programming models`#classification-of-parallel-programming-models]`_`f

• `F0af`_`[Process interaction`#process-interaction]`_`f

• `F0af`_`[Problem decomposition`#problem-decomposition]`_`f

• `F0af`_`[Terminology`#terminology]`_`f

• `F0af`_`[Example parallel programming models`#example-parallel-programming-models]`_`f

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[References`#references]`_`f

• `F0af`_`[Further reading`#further-reading]`_`f

-─

>>Classification of parallel programming models

Classifications of parallel programming models can be divided broadly into two areas: process interaction and problem decomposition.`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f]`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f]`:cite-ref-0-5-0[`F5bf`_`[5`#cite-note-0-5]`_`f]

>>>Process interaction

Process interaction relates to the mechanisms by which parallel processes are able to communicate with each other. The most common forms of interaction are shared memory and message passing, but interaction can also be implicit (invisible to the programmer).

>>>>Shared memory

Shared memory is an efficient means of passing data between processes. In a shared-memory model, parallel processes share a global address space that they read and write to asynchronously. Asynchronous concurrent access can lead to `F33f`_`[race conditions`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Race_condition]`_`f, and mechanisms such as `F33f`_`[locks`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Lock_(computer_science)]`_`f, `F33f`_`[semaphores`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Semaphore_(programming)]`_`f and `F33f`_`[monitors`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Monitor_(synchronization)]`_`f can be used to avoid these. Conventional `F33f`_`[multi-core processors`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multi-core_processor]`_`f directly support shared memory, which many parallel programming languages and libraries, such as `F33f`_`[Cilk`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cilk_(programming_language)]`_`f, `F33f`_`[OpenMP`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=OpenMP]`_`f and `F33f`_`[Threading Building Blocks`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Threading_Building_Blocks]`_`f, are designed to exploit.

>>>>Message passing

In a message-passing model, parallel processes exchange data through passing messages to one another. These communications can be asynchronous, where a message can be sent before the receiver is ready, or synchronous, where the receiver must be ready. The `F33f`_`[Communicating sequential processes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Communicating_sequential_processes]`_`f (CSP) formalisation of message passing uses synchronous communication channels to connect processes, and led to important languages such as `F33f`_`[Occam`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Occam_(programming_language)]`_`f, `F33f`_`[Limbo`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Limbo_(programming_language)]`_`f and `F33f`_`[Go`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Go_(programming_language)]`_`f. In contrast, the `F33f`_`[actor model`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Actor_model]`_`f uses asynchronous message passing and has been employed in the design of languages such as `F33f`_`[D`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=D_(programming_language)]`_`f, `F33f`_`[Scala`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Scala_(programming_language)]`_`f and SALSA.

>>>>Partitioned global address space

Partitioned Global Address Space (PGAS) models provide a middle ground between shared memory and message passing. PGAS provides a global memory address space abstraction that is logically partitioned, where a portion is local to each process. Parallel processes communicate by asynchronously performing operations (e.g. reads and writes) on the global address space, in a manner reminiscent of shared memory models. However by semantically partitioning the global address space into portions with affinity to a particular processes, they allow programmers to exploit `F33f`_`[locality of reference`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Locality_of_reference]`_`f and enable efficient implementation on `F33f`_`[distributed memory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Distributed_memory]`_`f parallel computers. PGAS is offered by many parallel programming languages and libraries, such as `F33f`_`[Fortran 2008`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Fortran_2008]`_`f, `F33f`_`[Chapel`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Chapel_(programming_language)]`_`f, UPC++, and `F33f`_`[SHMEM`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=SHMEM]`_`f.

>>>>Implicit interaction

In an implicit model, no process interaction is visible to the programmer and instead the compiler and/or runtime is responsible for performing it. Two examples of implicit parallelism are with `F33f`_`[domain-specific languages`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Domain-specific_language]`_`f where the concurrency within high-level operations is prescribed, and with `F33f`_`[functional programming languages`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Functional_programming]`_`f because the absence of `F33f`_`[side-effects`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Side_effect_(computer_science)]`_`f allows non-dependent functions to be executed in parallel.`:cite-ref-parfuncprog-6-0[`F5bf`_`[6`#cite-note-parfuncprog-6]`_`f] However, this kind of parallelism is difficult to manage`:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f] and functional languages such as `F33f`_`[Concurrent Haskell`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Concurrent_Haskell]`_`f and `F33f`_`[Concurrent ML`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Concurrent_ML]`_`f provide features to manage parallelism explicitly and correctly.

>>>Problem decomposition

A parallel program is composed of simultaneously executing processes. Problem decomposition relates to the way in which the constituent processes are formulated.`:cite-ref-8[`F5bf`_`[8`#cite-note-8]`_`f]`:cite-ref-0-5-1[`F5bf`_`[5`#cite-note-0-5]`_`f]

>>>>Task parallelism

A task-parallel model focuses on processes, or threads of execution. These processes will often be behaviourally distinct, which emphasises the need for communication. Task parallelism is a natural way to express message-passing communication. In `F33f`_`[Flynn's taxonomy`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Flynn's_taxonomy]`_`f, task parallelism is usually classified as `F33f`_`[MIMD`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multiple_instruction,_multiple_data]`_`f/`F33f`_`[MPMD`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Flynn's_taxonomy]`_`f or `F33f`_`[MISD`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multiple_instruction,_single_data]`_`f.

>>>>Data parallelism

A data-parallel model focuses on performing operations on a data set, typically a regularly structured array. A set of tasks will operate on this data, but independently on disjoint partitions. In `F33f`_`[Flynn's taxonomy`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Flynn's_taxonomy]`_`f, data parallelism is usually classified as `F33f`_`[MIMD`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multiple_instruction,_multiple_data]`_`f/`F33f`_`[SPMD`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=SPMD]`_`f or `F33f`_`[SIMD`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Single_instruction,_multiple_data]`_`f.

>>>>Stream Parallelism

Stream parallelism, also known as pipeline parallelism, focuses on dividing a computation into a sequence of stages, where each stage processes a portion of the input data. Each stage operates independently and concurrently, and the output of one stage serves as the input to the next stage. Stream parallelism is particularly suitable for applications with continuous data streams or pipelined computations.

>>>>Implicit parallelism

As with implicit process interaction, an implicit model of parallelism reveals nothing to the programmer as the compiler, the runtime or the hardware is responsible. For example, in compilers, `F33f`_`[automatic parallelization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Automatic_parallelization]`_`f is the process of converting sequential code into parallel code, and in computer architecture, `F33f`_`[superscalar execution`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Superscalar_processor]`_`f is a mechanism whereby `F33f`_`[instruction-level parallelism`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Instruction-level_parallelism]`_`f is exploited to perform operations in parallel.

>>Terminology

Parallel programming models are closely related to `F33f`_`[models of computation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Model_of_computation]`_`f. A model of parallel computation is an `F33f`_`[abstraction`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Abstraction]`_`f used to analyze the cost of computational processes, but it does not necessarily need to be practical, in that it can be implemented efficiently in hardware and/or software. A programming model, in contrast, does specifically imply the practical considerations of hardware and software implementation.`:cite-ref-9[`F5bf`_`[9`#cite-note-9]`_`f]

A parallel programming language may be based on one or a combination of programming models. For example, `F33f`_`[High Performance Fortran`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=High_Performance_Fortran]`_`f is based on shared-memory interactions and data-parallel problem decomposition, and `F33f`_`[Go`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Go_(programming_language)]`_`f provides mechanism for shared-memory and message-passing interaction.

>>Example parallel programming models

|---|---|---|---|

>>See also

• `F33f`_`[Automatic parallelization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Automatic_parallelization]`_`f

• `F33f`_`[Bridging model`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bridging_model]`_`f

• `F33f`_`[Concurrency`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Concurrent_computing]`_`f

• `F33f`_`[Degree of parallelism`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Degree_of_parallelism]`_`f

• `F33f`_`[Explicit parallelism`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Explicit_parallelism]`_`f

• `F33f`_`[List of concurrent and parallel programming languages`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=List_of_concurrent_and_parallel_programming_languages]`_`f

• `F33f`_`[Optical Multi-Tree with Shuffle Exchange`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Optical_Multi-Tree_with_Shuffle_Exchange]`_`f

• `F33f`_`[Parallel external memory (Model)`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Parallel_external_memory_(Model)]`_`f

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f Skillicorn, David B., "Models for practical parallel computation", International Journal of Parallel Programming, 20.2 133–158 (1991), https://www.ida.liu.se/~chrke55/papers/modelsurvey.pdf

`:cite-note-valiant1990-2`!2.`! `F0af`_`[↑`#cite-ref-valiant1990-2-0]`_`f Leslie G. Valiant, "A bridging model for parallel computation", Communications of the ACM, Volume 33, Issue 8, August, 1990, pages 103–111.

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f John E. Savage, Models of Computation: Exploring the Power of Computing, 2008, Chapter 7 (Parallel Computation), http://cs.brown.edu/~jes/book/ Archived 2016-11-05 at the `F33f`_`[Wayback Machine`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Wayback_Machine]`_`f

`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f "1.3 A Parallel Programming Model". `*www.mcs.anl.gov`*. Retrieved 2024-03-21.

`:cite-note-0-5`!5.`! `F0af`_`[↑`#cite-ref-0-5-0]`_`f "Introduction to Parallel Computing Tutorial | HPC @ LLNL". `*hpc.llnl.gov`*. Retrieved 2024-03-21.

`:cite-note-parfuncprog-6`!6.`! `F0af`_`[↑`#cite-ref-parfuncprog-6-0]`_`f Hammond, Kevin. Parallel functional programming: An introduction. In International Symposium on Parallel Symbolic Computation, p. 46. 1994.

`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f McBurney, D. L., and M. Ronan Sleep. "Transputer-based experiments with the ZAPP architecture." PARLE Parallel Architectures and Languages Europe. Springer Berlin Heidelberg, 1987.

`:cite-note-8`!8.`! `F0af`_`[↑`#cite-ref-8]`_`f "2.2 Partitioning". `*www.mcs.anl.gov`*. Retrieved 2024-03-21.

`:cite-note-9`!9.`! `F0af`_`[↑`#cite-ref-9]`_`f Skillicorn, David B., and Domenico Talia, Models and languages for parallel computation, ACM Computing Surveys, 30.2 123–169 (1998), https://www.cs.utexas.edu/users/browne/CS392Cf2000/papers/ModelsOfParallelComputation-Skillicorn.pdf

>>Further reading

• `:citerefblaise-barney`aBlaise Barney, `*Introduction to Parallel Computing`*, Lawrence Livermore National Laboratory, archived from the original on 2013-06-10, retrieved 2015-11-22

• `:citerefmurray-i-cole`aMurray I. Cole., `*Algorithmic Skeletons: Structured Management of Parallel Computation`* (PDF), University of Glasgow

• `:citerefj-darlintonm-ghanemh-w-to1993`aJ. Darlinton; M. Ghanem; H. W. To (1993). "Structured parallel programming". `*Proceedings of Workshop on Programming Models for Massively Parallel Computers`*. pp. 160–169. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1109/PMMP.1993.315543. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0-8186-4900-3. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 15265646.

• `:citerefian-foster`aIan Foster, `*Designing and Building Parallel Programs`*, Argonne National Laboratory

`c`F0af`_`[↑ Back to top`#top]`_`f`a